Cache 替换算法-近期最少使用 LRU

为每一个 Cache 块设置一个计数器（即每个 Cache 行额外需要一位替换位），用于记录每个 Cache 块已经有多久没有被访问了。当 Cache 满后，替换 Cache 计数器最大的，即使用最不频繁的块。有关于计数器的原则如下：

• 命中时，所命中的行的计数器清 0，其余不变；
• 未命中且还有空闲行时，新装入的计数器置 0，其余非空闲行全加 1；
• 未命中且无空闲行时，计数值最大的行的信息块被淘汰，新装行的块，计数器置 0，其余全加 1；

可见，该算法遵循了局部性原理，所以效率一般很高。但是若被频繁访问的主存块数量 > Cache 行的数量，则有可能发生抖动。